package vip.zhenzicheng.algorithm.leetcode.str;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters">无重复字符串的最长子串 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-19 14:27
 */
public class LongestSubstringWithoutRepeatingCharacters_3 {

  public int lengthOfLongestSubstring(String s) {
    // Hash结构记录当前字符以及上次出现的起始位置，用于后面跳转加速
    Map<Character, Integer> map = new HashMap<>();
    int len = s.length();
    int start = 0, max = 0;

    for (int cur = 0; cur < len; cur++) {
      char c = s.charAt(cur);
      if (map.containsKey(c)) { // 重复
        // start保存出现重复元素的上一次出现的位置
        start = Math.max(map.get(c) + 1, start);
      }
      max = Math.max(max, cur - start + 1); // 最长不重复序列长度
      map.put(c, cur); // 保存或更新字符出现的位置
    }
    return max;
  }
}
